package com.gitee.wsl.struct.tree.sample.trie

import com.gitee.wsl.func.consumer.Consumer
import kotlinx.atomicfu.locks.ReentrantLock
import kotlinx.atomicfu.locks.withLock

open class Trie<V> {
    private val rootNode = TrieNode<V>()

    private val lock: ReentrantLock = ReentrantLock()

    fun makeNode(pattern: List<String>, consumer: Consumer<TrieNode<V>>) {

//        lock.writeLock().lock()
//        try {
//            if (pattern.isEmpty()) {
//                consumer.accept(rootNode)
//            } else {
//                _makeNode(rootNode, pattern, 0, consumer)
//            }
//        } finally {
//            lock.writeLock().unlock()
//        }
        lock.withLock {
            if (pattern.isEmpty()) {
                consumer.accept(rootNode)
            } else {
                _makeNode(rootNode, pattern, 0, consumer)
            }
        }
    }

    private fun _makeNode(
        node: TrieNode<V>,
        pattern: List<String>,
        index: Int,
        consumer: Consumer<TrieNode<V>>,
    ) {
        val last = index == pattern.size - 1
        val name = pattern[index]
        val wildcard =  name.indexOf('{') >= 0
        var child: TrieNode<V>?
        if (wildcard) {
            child = node.wildcardChild
            if (child == null) {
                child = TrieNode()
                node.wildcardChild = child
            }
        } else {
            child = node.makeExactMatchChild(name)
        }

        if (last) {
            consumer.accept(child)
        } else {
            _makeNode(child, pattern, index + 1, consumer)
        }
    }

    fun match(path: List<String>): MatchResult<V>? {
        if (path.isEmpty()) return null

//        lock.readLock().lock()
//        try {
//            return _match(rootNode, path, 0, null)
//        } finally {
//            lock.readLock().unlock()
//        }

        lock.withLock {
            return _match(rootNode, path, 0, null)
        }
    }

    private fun _match(
        node: TrieNode<V>,
        path: List<String>,
        index: Int,
        candidate: TrieNode<V>?,
    ): MatchResult<V>? {
        var candidateVar = candidate
        val last = path.size == index + 1

        val name = path[index]
        val child = node.getExactMatchChild(name)
        if (child != null) {
            if (last) {
                if (child.value != null) {
                    // 严格匹配
                    candidateVar = child
                }
                return makeResult(path, candidateVar)
            } else {
                if (child.hasChild()) {
                    return _match(child, path, index + 1, candidateVar)
                }

                // 如果path只匹配了一部分，但是已经没有子模式能够匹配，则检查是否已经存在可匹配模式
                return makeResult(path, candidateVar)
            }
        } else {
            if (node.wildcardChild != null) {
                if (node.wildcardChild!!.isTillEnd) {
                    candidateVar = node.wildcardChild
                }
                return _match(node.wildcardChild!!, path, index + 1, candidateVar)
            } else {
                // 没有任何匹配的子节点，只能返回已经匹配的节点
                return makeResult(path, candidateVar)
            }
        }
    }

    fun makeResult(path: List<String>, candidate: TrieNode<V>?): MatchResult<V>? {
        if (candidate == null) return null
        return MatchResult(path, candidate.value!!)
    }
}